package com.seu.algorithms.graph.minispantree;

import java.util.Vector;

/**
 * 使用Prim算法求图的最小生成树
 *
 * @author liangfeihu
 * @since 2018/12/17 16:37
 */
public class LazyPrimMST<Weight extends Number & Comparable> {

    /**
     * 图的引用
     */
    private WeightedGraph<Weight> G;
    /**
     * 最小堆, 算法辅助数据结构
     */
    private MinHeap<Edge<Weight>> pq;
    /**
     * 标记数组, 在算法运行过程中标记节点i是否被访问
     */
    private boolean[] marked;
    /**
     * 最小生成树所包含的所有边
     */
    private Vector<Edge<Weight>> mst;
    /**
     * 最小生成树的权值
     */
    private Number mstWeight;

    /**
     * 构造函数, 使用Prim算法求图的最小生成树
     */
    public LazyPrimMST(WeightedGraph<Weight> graph) {

        // 算法初始化
        G = graph;
        pq = new MinHeap<Edge<Weight>>(G.E());
        marked = new boolean[G.V()];
        mst = new Vector<Edge<Weight>>();

        // Lazy Prim
        visit(0);
        while (!pq.isEmpty()) {
            // 使用最小堆找出已经访问的边中权值最小的边
            Edge<Weight> e = pq.extractMin();
            // 如果这条边的两端都已经访问过了, 则扔掉这条边
            // if (marked[e.v()] && marked[e.w()]) {
            if (marked[e.v()] == marked[e.w()]) {
                // 不是横切边就继续循环
                continue;
            }
            // 否则, 这条边则应该存在在最小生成树中
            mst.add(e);

            // 访问和这条边连接的还没有被访问过的节点
            if (!marked[e.v()]) {
                visit(e.v());
            } else {
                visit(e.w());
            }
        }

        // 计算最小生成树的权值
        mstWeight = mst.elementAt(0).wt();
        for (int i = 1; i < mst.size(); i++) {
            mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
        }
    }

    /**
     * 访问节点v
     */
    private void visit(int v) {
        assert !marked[v];

        marked[v] = true;

        // 将和节点v相连接的所有未访问的边放入最小堆中
        for (Edge<Weight> e : G.adj(v)) {
            // 横切边：一端已访问，另一端未访问
            if (!marked[e.other(v)]) {
                pq.insert(e);
            }
        }
    }

    /**
     * 返回最小生成树的所有边
     */
    public Vector<Edge<Weight>> mstEdges() {
        return mst;
    }

    /**
     * 返回最小生成树的权值
     */
    public Number result() {
        return mstWeight;
    }


    /**
     * 测试 Lazy Prim
     */
    public static void main(String[] args) {

        String filename = "F:\\projects\\design_pattern\\src\\main\\resources\\minitree\\testG1.txt";
        int V = 8;

        SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
        ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);

        // Test Lazy Prim MST
        System.out.println("Test Lazy Prim MST:");
        LazyPrimMST<Double> lazyPrimMST = new LazyPrimMST<Double>(g);
        Vector<Edge<Double>> mst = lazyPrimMST.mstEdges();
        for (int i = 0; i < mst.size(); i++) {
            System.out.println(mst.elementAt(i));
        }
        System.out.println("The MST weight is: " + lazyPrimMST.result());

        System.out.println();
    }

}
